#include <stdio.h>
#include <stdlib.h>

// 元素类型以整型为例
typedef int ElemType;
// 定义链表的结点数据结构
typedef struct LNode {
    ElemType data;
    struct LNode *next;
}LNode, *LinkList;

// 定义链栈的数据结构
//typedef struct {
//    LinkList L;     // 用链表存储的元素
//    int lenth;      // 标记链表的长度（栈中元素的个数）
//}LinkStack;

// 遍历打印
/**
 * 带头结点的链栈遍历打印栈中元素
 * @param L
 * @return
 */
bool PrintLinkStackWithHead(LinkList L) {
    if (L->next == NULL) {
        printf("NULL（栈为空）\n");
        return true;
    }
    while (L->next != NULL) {
        printf("%d ", L->next->data);
        L = L->next;
    }
    printf("\n");
    return true;
}
/**
 * 不带头结点的链栈遍历打印栈中元素
 * @param L
 * @return
 */
bool PrintLinkStackWithoutHead(LinkList L) {
    if (L == NULL) {
        printf("NULL（栈为空）\n");
        return true;
    }
    while (L != NULL) {
        printf("%d ", L->data);
        L = L->next;
    }
    printf("\n");
    return true;
}

// 创（初始化）
/*
 * 链栈的初始化就是初始化链表的过程，链头为栈顶
 * 若单独为栈定义一个数据结构，则可以额外设置一个参数存储栈中元素的个数，并初始化为0
 */
/**
 * 初始化一个带头结点的链表
 * 若初始化成功则返回true，失败则返回false
 * @param L 指向链栈的指针
 * @return
 */
bool InitLinkListWithHead(LinkList &L) {
    L = (LNode*)malloc(sizeof (LNode));
    if (L == NULL) {
        return false;
    }
    L->data = NULL;
    L->next = NULL;
    return true;
}
/**
 * 初始化一个不带头结点的链表
 * 若初始化成功则返回true，失败则返回false
 * @param L 指向链表的指针
 * @return
 */
bool InitLinkListWithoutHead(LinkList &L) {
    L = NULL;
    return true;
}

// 增（进栈）
/**
 * 带头结点链栈的进栈操作
 * 若进栈成功则返回true，失败则返回false
 * @param L 指向链栈的指针
 * @param e 要进栈的元素
 * @return
 */
bool PushWithHead(LinkList &L, ElemType e) {
    // 为新元素申请一个结点（同时也是链栈判满的操作）
    LNode *nodeNew = (LNode*) malloc(sizeof (LNode));
    if (nodeNew == NULL) {
        // 内存空间分配失败，返回false
        return false;
    }
    // 新结点赋值
    nodeNew->data = e;
    // 新结点入栈
    nodeNew->next = L->next;
    L->next = nodeNew;
    return true;
}
/**
 * 不带头结点链栈的进栈操作
 * 若进栈成功则返回true，失败则返回false
 * @param L 指向链栈的指针
 * @param e 要进栈的元素
 * @return
 */
bool PushWithoutHead(LinkList &L, ElemType e) {
    // 为新元素申请一个结点（同时也是链栈判满的操作）
    LNode *nodeNew = (LNode*) malloc(sizeof (LNode));
    if (nodeNew == NULL) {
        // 内存空间分配失败，返回false
        return false;
    }
    // 新结点赋值
    nodeNew->data = e;
    // 新结点入栈
    nodeNew->next = L;
    L = nodeNew;
    return true;
}

// 删（出栈）
/**
 * 带头结点链栈的出栈操作
 * 若成功则返回true，失败则返回false
 * @param L 指向链栈的指针
 * @param e 指向出栈元素的指针（使用了引用，因此可以将值从函数中带回）
 * @return
 */
bool PopWithHead(LinkList &L, ElemType &e) {
    // 带头结点的链栈判空，栈空则返回失败
    if (L->next == NULL) {
        return false;
    }
    // 暂存栈顶元素结点
    LNode *p = L->next;
    // 获取出栈元素，删除结点并释放空间
    e = p->data;
    L->next = p->next;
    free(p);
    return true;
}
/**
 * 不带头结点链栈的出栈操作
 * 若成功则返回true，失败则返回false
 * @param L 指向链栈的指针
 * @param e 指向出栈元素的指针（使用了引用，因此可以将值从函数中带回）
 * @return
 */
bool PopWithoutHead(LinkList &L, ElemType &e) {
    // 不带头结点的链栈判空，栈空则返回失败
    if (L == NULL) {
        return false;
    }
    // 暂存栈顶元素结点
    LNode *p = L;
    // 获取出栈元素，删除结点并释放空间
    e = p->data;
    L = p->next;
    free(p);
    return true;
}

// 查（获取栈顶元素）
/**
 * 带头结点链栈的获取栈顶元素操作
 * 若成功则返回栈顶元素的值，失败则返回NULL
 * @param L 指向链栈的指针
 * @return
 */
ElemType GetTopElemWithHead(LinkList L) {
    // 带头结点的链栈判空，栈空则返回NULL
    if (L->next == NULL) {
        return NULL;
    }
    return L->next->data;
}
/**
 * 不带头结点链栈的获取栈顶元素操作
 * 若成功则返回栈顶元素的值，失败则返回NULL
 * @param L 指向链栈的指针
 * @return
 */
ElemType GetTopElemWithoutHead(LinkList L) {
    // 不带头结点的链栈判空，栈空则返回NULL
    if (L == NULL) {
        return NULL;
    }
    return L->data;
}


/**
 * 操作带头结点的链栈
 */
void OperateLinkStackWithHead(LinkList &L) {
    bool endFlag = false;
    while (!endFlag) {
        printf("-----\n请选择操作：");
        printf("0 返回上一级菜单 1 元素入栈 2 查询栈顶元素 3 删除栈顶元素并输出 4 遍历打印当前栈\n请输入选项并按回车继续：");
        int choice;
        scanf("%d", &choice);
        switch (choice) {
            case 1: {
                ElemType e;
                printf("请输入要进栈的元素（整型数）：");
                scanf("%d", &e);
                if (PushWithHead(L, e)) {
                    printf("元素 %d 入栈成功\n", e);
                } else {
                    printf("元素 %d 入栈失败\n", e);
                }
                break;
            }
            case 2: {
                ElemType e;
                e = GetTopElemWithHead(L);
                if (e == NULL) {
                    printf("NULL\n");
                } else {
                    printf("当前栈顶元素为 %d\n", e);
                }
                break;
            }
            case 3: {
                ElemType e;
                if (PopWithHead(L, e)) {
                    printf("栈顶元素 %d 已出栈\n", e);
                } else {
                    printf("栈空，出栈失败\n");
                }
                break;
            }
            case 4: {
                PrintLinkStackWithHead(L);
                break;
            }
            default: {
                endFlag = true;
            }
        }// switch
    }// while
    return;
}
/**
 * 操作不带头结点的链栈
 */
void OperateLinkStackWithoutHead(LinkList &L) {
    bool endFlag = false;
    while (!endFlag) {
        printf("-----\n");
        printf("0 返回上一级菜单 1 元素入栈 2 查询栈顶元素 3 删除栈顶元素并输出 4 遍历打印当前栈\n请输入选项并按回车继续：");
        int choice;
        scanf("%d", &choice);
        switch (choice) {
            case 1: {
                ElemType e;
                printf("请输入要进栈的元素（整型数）：");
                scanf("%d", &e);
                if (PushWithoutHead(L, e)) {
                    printf("元素 %d 入栈成功\n", e);
                } else {
                    printf("元素 %d 入栈失败\n", e);
                }
                break;
            }
            case 2: {
                ElemType e;
                e = GetTopElemWithoutHead(L);
                if (e == NULL) {
                    printf("NULL\n");
                } else {
                    printf("当前栈顶元素为 %d\n", e);
                }
                break;
            }
            case 3: {
                ElemType e;
                if (PopWithoutHead(L, e)) {
                    printf("栈顶元素 %d 已出栈\n", e);
                } else {
                    printf("栈空，出栈失败\n");
                }
                break;
            }
            case 4: {
                PrintLinkStackWithoutHead(L);
                break;
            }
            default: {
                endFlag = true;
            }
        } // switch
    } // while
    return;
}

/**
 * 链栈的基本操作：创 增 删 查
 * @return
 */
int main() {
    printf("Hello, LinkStack!\n");
    bool endFlag = false;
    /*
     * 链栈的判空：判断链表中是否有元素，无则空，有则非空。
     * 链栈的判满：基本不存在满的情况。除非内存不够用，申请新结点的空间分配不足，则栈满。
     *              或者对栈的长度作出了特定的限制，则判断元素数量是否达到上限。
     */

    // 初始化 带头结点的链栈
    LinkList ListWithHead;
    if (InitLinkListWithHead(ListWithHead)) {
        printf("初始化带头结点的链栈成功！\n");
        PrintLinkStackWithHead(ListWithHead);
    } else {
        printf("初始化带头结点的链栈失败！\n");
    }
    // 初始化 不带头结点的链栈
    LinkList ListNoHead;
    if (InitLinkListWithoutHead(ListNoHead)) {
        printf("初始化不带头结点的链栈成功！\n");
        PrintLinkStackWithoutHead(ListNoHead);
    } else {
        printf("初始化带头结点的链栈失败！\n");
    }

    printf("完成链栈初始化..");
    while (!endFlag) {
        printf("\n=====\n请选择操作：");
        printf("0 结束程序 1 操作带头结点的链栈 2 操作不带头结点的链栈\n请输入选项并按回车继续：");
        int choice;
        scanf("%d", &choice);
        switch (choice) {
            case 1: {
                OperateLinkStackWithHead(ListWithHead);
                break;
            }
            case 2: {
                OperateLinkStackWithoutHead(ListNoHead);
                break;
            }
            default: {
                endFlag = true;
            }
        } // switch
    } // while

    printf("\nSee you next time~!\n");

    return 0;
}